package personal.leil.learning.insert;

import personal.leil.learning.utils.ArrayUtils;

/**
 * 插入排序
 * <p>
 * 插入排序代码实现
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2023-12-29
 */
public class InsertSort {

    /**
     * 插入排序逻辑实现
     *
     * @param arr 源数组
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            insertToSortedRange(arr, i);
        }
    }

    /**
     * 将数组r位置上的数插入0~r-1相应的位置，使数组在0~r范围内有序（0~r-1已经有序）
     *
     * @param arr 源数组
     * @param r   插入目标索引
     */
    public static void insertToSortedRange(int[] arr, int r) {
        // 从右向左比较，如果比左边的数小，就交换
        for (int i = r; i > 0; i--) {
            if (arr[i] < arr[i - 1]) {
                ArrayUtils.swapByXOR(arr, i, i - 1);
            } else {
                break;
            }
        }
    }

    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArr(20);
        System.out.println("before sort:");
        ArrayUtils.printArr(arr);
        insertSort(arr);
        System.out.println("after sort:");
        ArrayUtils.printArr(arr);
    }

}
